package com.jia.leetCode;

import java.util.Random;

/**
 * 1206.跳表实现
 *
 *
 */
public class Pro1206 {

    static class Node {
        int val;
        Node right, down;
        public Node(Node r, Node d, int val) {
            this.val = val;
            this.right = r;
            this.down = d;
        }
    }

    Node head = new Node(null, null, 0);
    Node[] stack = new Node[64];//2^64相当大
    public Pro1206() {

    }

    public boolean search(int target) {
        //从左往右，缩小区间，然后向下
        for(Node p = head; p!=null; p = p.down) {
            while(p.right!=null && p.right.val < target) {
                p = p.right;
            }
            if(p.right != null && p.right.val == target) {
                return true;
            }
        }
        return false;
    }
    Random random = new Random();
    public void add(int num) {
        int lv = -1;
        for(Node p = head; p != null; p = p.down) {
            while(p.right != null && p.right.val < num) {
                p = p.right;
            }
            stack[++lv] = p;//从顶到下
        }
        //从下到顶
        boolean insertUp = true;//最底的必须插入
        Node downNode = null;
        while(insertUp && lv>=0) {
            Node insert = stack[lv--];
            Node next = insert.right;
            insert.right = new Node(insert.right, downNode, num);
            insert.right.right = next;
            downNode = insert.right;
            //通过硬币决定上一层num是否可选
            insertUp = (random.nextInt() & 1) == 0;
        }
        if(insertUp) {
            head = new Node(new Node(null, downNode, num), head, 0);
        }
    }

    /**
     * 跳表删除一个元素num，如果存在就删除一个，返回true，否则返回false
     * @param num
     * @return
     */
    public boolean erase(int num) {
        boolean exists = false;
        for(Node p = head; p != null; p = p.down) {
            while(p.right!=null && p.right.val < num) {
                p = p.right;
            }
            if(p.right != null && p.right.val == num) {
                exists = true;
                p.right = p.right.right;
            }
        }
        return exists;
    }
}
